package edu.pw.elka.gtsna.graph_algorithms;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

import edu.pw.elka.gtsna.graph.Graph;


/**
 * @author szczepan
 *
 * This algorithm find all articulation points in connected subgraph in time O(V+E)
 * It runs DFS search, and each node v is pivotal if from some of his children (or his descendant)
 * there is no "back edge" to some node above v
 *
 */

public class FindPivotal {

	/* Graph where we want to find articulation (pivotal) points */
	Graph graph;
	
	/* The connected component of the graph to which we are restricted */
	Set<Integer> subgraph;
	
	/* Pivotal nodes */
	Set<Integer> pivotals;
	
	/* Information about nodes */
	private class NodeInformation{
		public NodeInformation(){
			treeLevel   =  0;	
			lowest      =  0;	
			dfsNumber   = -1;	// number -1 mean unvisited node
			numChildren =  0;	
		}
		public int treeLevel;	// the level in DFS search
		public int lowest;		// the node with lowest number at each some of descendant is pointing
		public int dfsNumber;	// ordering of visiting nodes
		public int numChildren; // number of children
	}
		
	/* Information about each node in the subgraph */
	Map <Integer, NodeInformation> nodeInfo;
		
	public FindPivotal(Graph graph, Set<Integer> subgraph){
		this(graph);
		this.subgraph = subgraph;
		for(int v: subgraph){
			nodeInfo.put(v, new NodeInformation());
		}
	}
	
	public FindPivotal(Graph graph){
		this.graph=graph;
		pivotals = new LinkedHashSet<Integer>();
		nodeInfo = new HashMap<Integer, NodeInformation>();
	}
	
	public void calculatePivotals(){
		runFindPivotals(subgraph.iterator().next());
	}
	
	public void runFindPivotals(int node){
		pivotals.clear();
		getPivotal(node);
	}
	
	/* dfsCounter labels nodes in DFS in the order of visiting */
	int dfsCounter = 1;
	
	/* This is recursive function creating DFS tree */
	private void getPivotal(int root){
		nodeInfo.get(root).dfsNumber = dfsCounter++;
		nodeInfo.get(root).lowest = nodeInfo.get(root).dfsNumber;
		
	//	System.out.println(root);
		
		for(int u: graph.getNeigbours(root)){
			
			/* We limit our search to a given connected subgraph */
			if (!subgraph.contains(u))
				continue;
			
			/* This node haven't been yet visited */
			if (nodeInfo.get(u).dfsNumber == -1) {
				nodeInfo.get(u).treeLevel = nodeInfo.get(root).treeLevel+1;
				nodeInfo.get(root).numChildren++;
				getPivotal(u);
				nodeInfo.get(root).lowest = Math.min(nodeInfo.get(root).lowest, nodeInfo.get(u).lowest);
				if (nodeInfo.get(root).dfsNumber == 1){
					if (nodeInfo.get(root).numChildren > 1) {
						/* Root is pivotal node only if it has more then one children */
						pivotals.add(root);
					}
				} else {
					if (nodeInfo.get(u).lowest >= nodeInfo.get(root).dfsNumber){
						/* If we remove root, u will be disconnected, because it 
						 * does not point to any node higher than root */
						pivotals.add(root);
					}				
				}
			/* We have visited node u, so this is "back edge" in DFS algorithm */
			} else {
				if (nodeInfo.get(u).treeLevel < nodeInfo.get(root).treeLevel-1){
					/* We meet "back edge" that can points to low node */
					nodeInfo.get(root).lowest = Math.min(nodeInfo.get(root).lowest, nodeInfo.get(u).dfsNumber);
				}
			}			
		}
		
	}

	public Set<Integer> getSubgraph() {
		return subgraph;
	}

	public void setSubgraph(Set<Integer> subgraph) {
		this.subgraph = subgraph;
		nodeInfo.clear();
		for(int v: subgraph){
			nodeInfo.put(v, new NodeInformation());
		}
		dfsCounter = 1;
	}


	public Set<Integer> getPivotals() {
		return pivotals;
	}


	public void setPivotals(Set<Integer> pivotals) {
		this.pivotals = pivotals;
	}
	
	public Boolean isPivotal(int i) {
		if (subgraph!=null && subgraph.size()==1)
			return false;
		return pivotals.contains(i);
	}
	
	public void addPivotals(Set<Integer> pivo) {
		pivotals.addAll(pivo);
	}
	
	public void removePivotals(Set<Integer> pivo) {
		pivotals.removeAll(pivo);
	}
	public void clearPivotals() {
		pivotals.clear();
	}
	
	
}
